"""见算法导论"""
import random
import math

#分解成2^t*d的形式。
def divide(num):
    t = 0
    while True:
        if num%2 == 0:
            num = int(num/2)
            t += 1
        else:
            break
    return (t, num)

#a^t mod(num)
def mod(a,t,num):
    b = 1
    while t > 0:
        if t%2 == 1:
            b = b*a%num
        a = a*a%num
        t = math.floor(t/2)
    return b

#Miller-Robin
def isPrime(num, a):
    t, d = divide(num - 1)
    i = 0
    x1 = mod(a, d, num)
    while i < t:
        x2 = x1**2%num
        if x2 == 1 and x1 != 1 and x1 != num-1:
            return False
        x1 = x2
        i += 1
    if x1 != 1:
        return False
    return True

def miller(num):
    #num = int(input("Please enter the number: "))
    if num == 2:
        return True
    for i in range(50):
        s = random.randint(2,num - 1)
        if not isPrime(num, s):
            return False
    return True

def millerobin():
    num = int(input("Please enter the number: "))
    print(miller(num))


        
        

